package _go

//空间优越过的方案 因为dptable只跟前一天有关 所以只记录两个数就可以了
func maxProfit(prices []int) int {

	dp := make([]int, 2)

	dp[0] = 0
	dp[1] = -prices[0]

	for i := 1; i < len(prices); i++ {
		dp[0] = max(dp[0], prices[i]+dp[1])
		dp[1] = max(dp[1], dp[0]-prices[i])
	}

	//最后一天不持有股票是最大收益
	return dp[0]
}

/*dp 数组的定义
dp[i][0] 第i天不吃油股票的最大收益
	公式定义	: 不持有股票的最大收益是 前一天不持有股票的最大收益 和
				前一天持有股票的最大收益加上当前的股票价值（因为要买点当前股票才符合dp[i][0]定义）
	dp[i][0] = max(dp[i][0], prices[i] + dp[i-1][1])//

dp[i][1] 第i天持有股票的最大收益
	公式定义	: 第i天持有股票的最大收益 是前一天持有股票的最大收益 和
				前一天不持有股票的最大收益减去当天股票的价值（因为要买回来当前股票才符合定义）
	dp[i][1] = max(dp[i][1], dp[i-1][0] - prices[i])
*/
func maxProfit2(prices []int) int {

	dp := make([][2]int, len(prices))

	dp[0][0] = 0
	dp[0][1] = -prices[0]

	for i := 1; i < len(prices); i++ {
		dp[i][0] = max(dp[i][0], prices[i]+dp[i-1][1]) //
		dp[i][1] = max(dp[i][1], dp[i-1][0]-prices[i])
	}

	//最后一天不持有股票是最大收益
	return dp[0]
}
func max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}
